import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author VernHe
 * @date 2021年06月26日 22:32
 */
public class Solution_0239 {
    public static void main(String[] args) {
//        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int[] nums = new int[]{1, -1};
        int k = 1;
        int[] res = new Solution_0239().maxSlidingWindow(nums, k);
        for (int re : res) {
            System.out.printf(re + "_");
        }
        System.out.println();
    }

    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        int currMaxValue = Integer.MIN_VALUE;
        // 初始化currMaxValue
        for (int i = 0; i < k; i++) {
            if (currMaxValue < nums[i]) {
                currMaxValue = nums[i];
            }
        }
        System.out.println("初始化后currMaxValue = " + currMaxValue);
        int[] res;
        if (nums.length > k) {
            res = new int[nums.length - k + 1];
            res[0] = currMaxValue;
            for (int i = k; i < nums.length; ) {
                if (currMaxValue < nums[i]) {
                    currMaxValue = nums[i];
                }
                i++;
                res[i - k] = currMaxValue;
            }

        } else {
            res = new int[1];
            res[0] = currMaxValue;
        }
        return res;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        // 定义优先队列并初始化
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        // 定义返回的结果
        int[] res = new int[nums.length - k + 1];
        // 循环
        for (int i = 0; i < res.length; i++) {
            res[i] = queue.poll();
            if (i < res.length - 1) {
                // 往后移动
                queue.add(nums[k + i]);
                queue.remove(nums[i]);
            }
        }
        return res;
    }

    /**
     * 为防止出现remove的时候删除所有相同元素，存的时候，[存值+下标]
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] pair1, int[] pair2) {
                // 优先比值
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i], i});
        }
//        System.out.println("初始化后：");
//        queue.forEach(a -> {
//            System.out.printf(a[0] + "_" + a[1] + ", ");
//        });
//        System.out.println();
        // 定义返回的结果
//        System.out.println("peek" + queue.peek());
        int[] res = new int[nums.length - k + 1];
        res[0] = queue.peek()[0];
        // 循环
        for (int i = k; i < nums.length; i++) {
            // 右边加一个
            queue.offer(new int[]{nums[i], i});
            // 左边移出
            while (queue.peek()[1] <= i - k) {
                queue.poll();
            }
            res[i - k +1] = queue.peek()[0];
        }
        return res;
    }
}
/**
 * k = 3   i = 0
 * [1,3,-1,-3,5,3,6,7]
 * [1,3,-1]
 * <p>
 * k = 3   1 = 1
 * [1,3,-1,-3,5,3,6,7]
 * [3,-1,-3]
 */

